<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>
    /**
     * https://leetcode-cn.com/problems/trapping-rain-water/
     * https://leetcode-cn.com/problems/trapping-rain-water/solution/42jie-yu-shui-by-lisa-6-2/
     * 思路：
     * 1.首先题目的要求是求解出所有排列的柱子，下雨之后能接多少雨水，我们可以先求解出每一列上所能
     *   接雨水的面积
     * 
     * 2.那么如何求解当前位置（每一列）上的面积呢？
     *   ● 因为宽度为1，所以每一列上的面积 = Math.min(left_max[i], right_max[i]) - height[i];
     *   ● 开两个数组先记录下当前位置上左右两边高度的最大值，通过遍历不断更新最大值来记录
     */ 
    let height = [0,1,0,2,1,0,1,3,2,1,2,1]; //output 6

    function trap(height) {
      let n = height.length;
      if (n === 0) return 0;
      let res = 0;
      let left_max = [], right_max = [];

      left_max[0] = height[0];
      for (let i = 1; i < n; i++)
        left_max[i] = Math.max(left_max[i-1], height[i])
      
      right_max[n-1] = height[n-1];
      for (let i = n-2; i >=0; i--)
        right_max[i] = Math.max(right_max[i+1], height[i])
      
      for (let i = 0; i < n; i++)
        res += Math.min(left_max[i], right_max[i]) - height[i]

      return res;
    }
    console.log(trap(height));
  </script>
</body>
</html>